package top.minuy.subject.costom.bfs;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

/**
 * 一道智力题
 * 农夫需要把狼、羊、菜和自己运到河对岸去，
 * 只有农夫能够划船，而且船比较小。
 * 除农夫之外每次只能运一种东西，
 * 还有一个棘手问题，就是如果没有农夫看着：
 * 羊会偷吃菜，狼会吃羊。
 * 请考虑一种方法，
 * 让农夫能够安全地安排这些东西和他自己过河。
 *
 * @author Minuy
 * @time 8:57
 * @date 2021/11/21
 */
public class FarmerTransport {
    //       人  狼  羊  菜
    //  源： 0   0   0   0
    //目标： 1   1   1   1

    String s = "0000";
    String t = "1111";
    HashMap<String, String> pre; // 记录
    HashMap<String, String> des; // 描述

    public FarmerTransport() {
        pre = new HashMap<>();
        des = new HashMap<>();

        ArrayList<String> queue = new ArrayList<>();

        if (isFailed(s)) {
            return;
        }

        String sta = s;
        queue.add(sta);
        pre.put(sta, sta);
        while (!queue.isEmpty()) {
            sta = queue.remove(0);

            HashMap<String, String> nextSta = getNextSta(sta);

            for (String curSta : nextSta.keySet()) {
                if (!pre.containsKey(curSta)) { // 如果还没访问过
                    queue.add(curSta);
                    pre.put(curSta, sta); // 记录父顶点
                    des.put(sta + curSta, nextSta.get(curSta));  // 记录过程描述
                    if (curSta.equals(t)) {
                        return;
                    }
                }
            }
        }
    }

    private HashMap<String, String> getNextSta(String sta) {
        HashMap<String, String> nextSta = new HashMap<>();
        char[] chars = sta.toCharArray();
        char backup;
        String n;
        if (chars[0] == '1') {//在1这一侧（东）
            chars[0] = '0'; // 农夫从1到0这一侧
            n = new String(chars);
            if (!isFailed(n)) {
                nextSta.put(n, "农夫从东侧到西侧");
            }
            //------------------------
            backup = chars[1]; // 备份
            if (chars[1] == '1') { // 如果狼在这边
                chars[1] = '0'; // 带狼过去
                n = new String(chars);
                if (!isFailed(n)) {
                    nextSta.put(n, "农夫从东侧带狼到西侧");
                }
            }
            chars[1] = backup; // 恢复
            //------------------------
            backup = chars[2]; // 备份
            if (chars[2] == '1') { // 如果羊在这边
                chars[2] = '0'; // 带羊过去
                n = new String(chars);
                if (!isFailed(n)) {
                    nextSta.put(n, "农夫从东侧带羊到西侧");
                }
            }
            chars[2] = backup;// 恢复
            //------------------------
            backup = chars[3];// 备份
            if (chars[3] == '1') { // 如果菜在这边
                chars[3] = '0'; // 带菜过去
                n = new String(chars);
                if (!isFailed(n)) {
                    nextSta.put(n, "农夫从东侧带菜到西侧");
                }
            }
            chars[3] = backup;// 恢复
        } else if (chars[0] == '0') {
            chars[0] = '1'; // 农夫从0到1这一侧
            n = new String(chars);
            if (!isFailed(n)) {
                nextSta.put(n, "农夫从西侧到东侧");
            }
            //------------------------
            backup = chars[1]; // 备份
            if (chars[1] == '0') { // 如果狼在这边
                chars[1] = '1'; // 带狼过去
                n = new String(chars);
                if (!isFailed(n)) {
                    nextSta.put(n, "农夫从西侧带狼到东侧");
                }
            }
            chars[1] = backup; // 恢复
            //------------------------
            backup = chars[2]; // 备份
            if (chars[2] == '0') { // 如果羊在这边
                chars[2] = '1'; // 带羊过去
                n = new String(chars);
                if (!isFailed(n)) {
                    nextSta.put(n, "农夫从西侧带羊到东侧");
                }
            }
            chars[2] = backup;// 恢复
            //------------------------
            backup = chars[3];// 备份
            if (chars[3] == '0') { // 如果菜在这边
                chars[3] = '1'; // 带菜过去
                n = new String(chars);
                if (!isFailed(n)) {
                    nextSta.put(n, "农夫从西侧带菜到东侧");
                }
            }
            chars[3] = backup;// 恢复
        }
        return nextSta;
    }

    public Iterable<String> process() {
        ArrayList<String> res = new ArrayList<>();
        if (!pre.containsKey(t)) {
            return res;
        }
        String cur = t;
        while (!cur.equals(s)) {
            res.add(cur);
            cur = pre.get(cur);
        }
        res.add(s);
        Collections.reverse(res);

        ArrayList<String> ret = new ArrayList<>();
        String p = res.get(0);
        for (int i = 1; i < res.size(); i++) {
            ret.add("状态 : " + getStaDes(p));
            ret.add("步骤 : " + i);
            String s = res.get(i);
            ret.add("操作 : " + des.get(p + s));
            p = s;
        }
        ret.add("状态 : " + getStaDes(p));
        return ret;
    }

    private String getStaDes(String sta) {
        char[] s = sta.toCharArray();
        char[] dc = new char[6], xc = new char[6];
        ArrayList<Character> d = new ArrayList<>(), x = new ArrayList<>(), c = null;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '1') {
                c = d;
            } else {
                c = x;
            }

            if (i == 0) {
                c.add('人');
            } else if (i == 1) {
                c.add('狼');
            } else if (i == 2) {
                c.add('羊');
            } else if (i == 3) {
                c.add('菜');
            }
        }

        dc[0] = '东';
        xc[0] = '西';
        dc[1] = '：';
        xc[1] = '：';

        for (int i = 2; i < dc.length; i++) {
            dc[i] = '空';
        }
        for (int i = 2; i < xc.length; i++) {
            xc[i] = '空';
        }

        for (int i = 0; i < d.size(); i++) {
            dc[i + 2] = d.get(i);
        }
        for (int i = 0; i < x.size(); i++) {
            xc[i + 2] = x.get(i);
        }

        return new String(xc) + " | " + new String(dc);
    }

    private boolean isFailed(String sta) {
        char[] part = sta.toCharArray();
        if (part[0] == '0') {
            if (part[1] == '1' && part[2] == '1') { // 狼和羊，没有农夫
                return true;
            }
            if (part[2] == '1' && part[3] == '1') { // 菜和羊，没有农夫
                return true;
            }
        } else if (part[0] == '1') {
            if (part[1] == '0' && part[2] == '0') { // 狼和羊，没有农夫
                return true;
            }
            if (part[2] == '0' && part[3] == '0') { // 菜和羊，没有农夫
                return true;
            }
        }
        return false;
//        char[] part1 = sta.toCharArray();
//        char[] part2 = new char[part1.length];
//        for (int i=0;i<part1.length;i++){
//            if (part1[i] == '1'){
//            part2[i] = '0';
//            }else if (part1[i] == '0'){
//                part2[i] = '1';
//            }
//        }
//
//        if(part1[0] == '0'){
//            if(part2[1])
//        }

    }

    public static void main(String[] args) {
        FarmerTransport ft = new FarmerTransport();
        for (String s : ft.process()) {
            System.out.println(s);
        }
    }
}
